package tree

import "fmt"

type BTreeNode struct {
	Data       interface{}
	RightChild *BTreeNode
	LeftChild  *BTreeNode
	Parent     *BTreeNode `json:"-"`
}

//前序遍历:从根开始往下,先左后右
func PreOrder(bt *BTreeNode) {
	if bt != nil {
		fmt.Print(bt.Data)
		PreOrder(bt.LeftChild)
		PreOrder(bt.RightChild)
	}
}

//中序遍历:先左子节点再自己再右子节点
func MidOrder(bt *BTreeNode) {
	if bt != nil {
		MidOrder(bt.LeftChild)
		fmt.Print(bt.Data)
		MidOrder(bt.RightChild)
	}
}

//先左后右再自己
func PostOrder(bt *BTreeNode) {
	if bt != nil {
		PostOrder(bt.LeftChild)
		PostOrder(bt.RightChild)
		fmt.Print(bt.Data)
	}
}

//层次遍历,把同层的遍历完成,再遍历下层.从左至右.
func LevelOrder(bt *BTreeNode) {
	queue := []*BTreeNode{}
	if bt != nil {
		queue = append(queue, bt)
		for len(queue) > 0 {
			curr := queue[0]
			queue = queue[1:]
			fmt.Print(curr.Data)
			if curr.LeftChild != nil {
				queue = append(queue, curr.LeftChild)
			}
			if curr.RightChild != nil {
				queue = append(queue, curr.RightChild)
			}

		}
	}
}
